package com.yiwenup.struct._05_unionfind;

/**
 * 并查集：快速查找实现
 * 基于 size 的优化，避免可能出现退化到链表结构的情况：合并的时候，【元素】少的树，挂到【元素】多的树上
 * <p>
 * 时间复杂度：find - O(logn)；union - O(logn)
 **/
public class QuickUnionV2 extends QuickUnionV1 {

    /**
     * 保存每个元素，以它作为更节点的树的节点个数
     */
    private final int[] sizes;

    public QuickUnionV2(int capacity) {
        super(capacity);
        sizes = new int[capacity];
        for (int i = 0; i < parents.length; i++) {
            sizes[i] = 1;
        }
    }

    /**
     * 基于 size 的优化
     * 将 {@param v1} 所在集合的根节点设置为  {@param v2} 的根节点
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        if (sizes[p1] < sizes[p2]) {
            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        } else {
            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }
    }
}
